package com.zj.base;

import java.util.Arrays;

/**
 * @program algorithm
 * @description:
 * @author: zhangbo
 * @create: 2022/07/20 23:18
 */
public class MergeSort2 {


    private int[] arr = new int[]{5, 3, 6, 8, 1, 7, 9, 4, 2};

    public void sort(int[] arr, int l, int r) {

        int mid = (r - l) / 2 + l;
        if (l < r) {
            sort(arr, l, mid);
            sort(arr, mid + 1, r);
            this.marge(arr, l, mid, r);
            System.out.println(Arrays.toString(arr));
        }


    }


    /**
     * 这个方法就是考察两个数组按照大小排序
     * 方法：
     * 使用双指针的方法
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private void marge(int[] arr, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        //左指针
        int i = l;
        //右指针
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= r) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 把右边剩余的数移入数组
        while (j <= r) {
            temp[k++] = arr[j++];
        }

        for (int m = 0; m < temp.length; m++) {
            arr[l + m] = temp[m];
        }

    }

    public static void main(String[] args) {
        MergeSort2 m = new MergeSort2();
        m.sort(m.arr, 0, m.arr.length - 1);
    }



    private void marge02(){

    }


}
